package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-15 19:32
 */
public class n_10_2 {
    public static void main(String[] args) {

    }

    public int count=0;

    /**
     * 思路!!!
     *   当 n 为 1 时，只有一种覆盖方法
     *   当 n 为 2 时，有两种覆盖方法
     *   要覆盖 2*n 的大矩形，可以先覆盖 2*1 的矩形，再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，再覆盖 2*(n-2) 的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。
     * 类似于斐波那契数列!
     * @param target
     * @return
     */
    public int rectCover(int target) {
        if (target<=2){
            return target;
        }
        int pre1=2;
        int pre2=1;
        int sum=0;
        for (int i = 3; i <= target; i++) {
            sum=pre1+pre2;
            pre2=pre1;
            pre1=sum;
        }
        return sum;
    }

}
